package zcw.com.lib_leet_code;

import java.util.HashSet;
import java.util.Set;

/**
 * Created by 朱城委 on 2021/7/15.<br><br>
 *
 * 最长回文串
 */
public class Topic409 {

    public static void main(String[] args) {
        Topic409 instance = new Topic409();

        System.out.println(instance.longestPalindrome("abccccdd"));
        System.out.println(instance.longestPalindrome("a"));
        System.out.println(instance.longestPalindrome("bb"));
    }

    public int longestPalindrome(String s) {
        int[] map = new int[52];
        for(char ch : s.toCharArray()) {
            if(ch >= 'A' && ch <= 'Z') {
                map[ch - 'A']++;
            }
            else {
                map[ch - 'a' + 26]++;
            }
        }

        int single = 0;
        int counter = 0;
        for(int value : map) {
            if((value & 1) == 1) {
                single = 1;
            }

            counter += value / 2;
        }

        return counter * 2 + single;
    }

    public int longestPalindrome2(String s) {
        Set<Character> set = new HashSet<>();
        int counter = 0;
        for(char ch : s.toCharArray()) {
            if(set.contains(ch)) {
                set.remove(ch);
                counter += 2;
            }
            else {
                set.add(ch);
            }
        }

        if(!set.isEmpty()) {
            counter++;
        }

        return counter;
    }
}
